class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>> dp(n,vector<int>(3));
        dp[0][nums[0]%3]=nums[0];
        for(int i=1;i<n;i++)
        {
            if(nums[i]%3==0)
            {
                dp[i][0]=dp[i-1][0]+nums[i];
                if(dp[i-1][1]) dp[i][1]=dp[i-1][1]+nums[i];
                if(dp[i-1][2]) dp[i][2]=dp[i-1][2]+nums[i];
            }
            else if(nums[i]%3==1)
            {
                dp[i][0]=dp[i-1][0];
                dp[i][2]=dp[i-1][2];

                if(dp[i-1][2])dp[i][0]=max(dp[i-1][0],dp[i-1][2]+nums[i]);
                dp[i][1]=max(dp[i-1][1],dp[i-1][0]+nums[i]);
                if(dp[i-1][1])dp[i][2]=max(dp[i-1][2],dp[i-1][1]+nums[i]);

            }
            else
            {

                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1];

                if(dp[i-1][1])dp[i][0]=max(dp[i-1][0],dp[i-1][1]+nums[i]);
                 if(dp[i-1][2])dp[i][1]=max(dp[i-1][1],dp[i-1][2]+nums[i]);
                dp[i][2]=max(dp[i-1][2],dp[i-1][0]+nums[i]);
            }
            //cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;

        }

        return dp[n-1][0];


    }
};